package com.fw.algorithm.sort;

import java.util.Arrays;

/**
 * 基数排序（桶排序思路相似）
 */
public class RadixSort {

    public static void main(String[] args) {
        int [] arr = {53, 3, 542, 748, 14, 214};
        radixSort(arr);
    }

    /**
     * 最终版
     */
    public static void radixSort(int ...arr){

        // 初始化桶 由于不清楚每个桶需要装载多少值，最综合的做法就是 使用 原始元素的长度。
        int[][] spaceArr = new int[10][arr.length];
        // 初始化桶 装载数据的下标索引。  10
        int [] spaceArrIndex = new int[spaceArr.length];
        // 求出最大的 数据长度
        int max = arr[0];
        for (int j = 1; j < arr.length; j++) {
            if (arr[j] > max){
                max = arr[j];
            }
        }
        // 算出长度
        int numberLen = (max + "").length();
        for (int i = 0,n = 1; i < numberLen; i++,n *= 10) {

            // 开始第二次执行分析
            // 装载桶数据
            for (int l = 0; l < arr.length; l++) {
                // 算出十位数
                int resultNum = arr[l] / n % 10;
                // 放置桶中
                spaceArr[resultNum][spaceArrIndex[resultNum]] = arr[l];
                spaceArrIndex[resultNum]++;
            }
            // 将桶数据放置到 原始数组中
            // arr 中 的索引
           int index = 0;
            for (int j = 0; j < spaceArr.length; j++) {
                // 证明是有数据的那么就开始执行
                if (spaceArrIndex[j]!= 0 ){
                    for (int k = 0; k < spaceArrIndex[j]; k++) {
                        arr[index ++ ] = spaceArr[j][k];
                    }
                }
                // 将记录桶数据索引的数组重置为 0
                spaceArrIndex[j] = 0;

            }
        }
        System.out.printf("排序:%s\n", Arrays.toString(arr));

    }


    /**
     * 分析版
     */
    public static void radixShowSort(int ...arr){
        /**
         * 大概思路是这样的。
         *  为什么是10 ？ 假设 784 是一个整数，其实所有的数都是 个位数，十位数，百位数，千位数，万位数 组成的。分解后 都是 个体！
         * 1. 要根据元素的 个位数，十位数，百位数 进行分桶存储，所以需要一个 二维数组，当作桶下标，以及存储装载的元素
         * 2. 需要一个记录二维数组装载数据的索引值。
         */
        // 初始化桶 由于不清楚每个桶需要装载多少值，最综合的做法就是 使用 原始元素的长度。
        int[][] spaceArr = new int[10][arr.length];
        // 初始化桶 装载数据的下标索引。  10
        int [] spaceArrIndex = new int[spaceArr.length];
        // 开始第一次执行分析
        // 装载桶数据
        for (int l = 0; l < arr.length; l++) {
            // 算出个位数
            int resultNum = arr[l] / 1 % 10;
            // 放置桶中
            spaceArr[resultNum][spaceArrIndex[resultNum]] = arr[l];
            spaceArrIndex[resultNum]++;
        }
        // 将桶数据放置到 原始数组中
        // arr 中 的索引
        int index = 0;
        for (int j = 0; j < spaceArr.length; j++) {
            // 证明是有数据的那么就开始执行
            if (spaceArrIndex[j]!= 0 ){
                for (int k = 0; k < spaceArrIndex[j]; k++) {
                    arr[index ++ ] = spaceArr[j][k];
                }
            }
            // 将记录桶数据索引的数组重置为 0
            spaceArrIndex[j] = 0;

        }
        System.out.printf("第一次排序:%s\n", Arrays.toString(arr));




        // 开始第二次执行分析
        // 装载桶数据
        for (int l = 0; l < arr.length; l++) {
            // 算出十位数
            int resultNum = arr[l] / 10 % 10;
            // 放置桶中
            spaceArr[resultNum][spaceArrIndex[resultNum]] = arr[l];
            spaceArrIndex[resultNum]++;
        }
        // 将桶数据放置到 原始数组中
        // arr 中 的索引
         index = 0;
        for (int j = 0; j < spaceArr.length; j++) {
            // 证明是有数据的那么就开始执行
            if (spaceArrIndex[j]!= 0 ){
                for (int k = 0; k < spaceArrIndex[j]; k++) {
                    arr[index ++ ] = spaceArr[j][k];
                }
            }
            // 将记录桶数据索引的数组重置为 0
            spaceArrIndex[j] = 0;

        }
        System.out.printf("第二次排序:%s\n", Arrays.toString(arr));




        // 开始第三次执行分析
        // 装载桶数据
        for (int l = 0; l < arr.length; l++) {
            // 算出百位数
            int resultNum = arr[l] / 100 % 10;
            // 放置桶中
            spaceArr[resultNum][spaceArrIndex[resultNum]] = arr[l];
            spaceArrIndex[resultNum]++;
        }
        // 将桶数据放置到 原始数组中
        // arr 中 的索引
        index = 0;
        for (int j = 0; j < spaceArr.length; j++) {
            // 证明是有数据的那么就开始执行
            if (spaceArrIndex[j]!= 0 ){
                for (int k = 0; k < spaceArrIndex[j]; k++) {
                    arr[index ++ ] = spaceArr[j][k];
                }
            }
            // 将记录桶数据索引的数组重置为 0
            spaceArrIndex[j] = 0;

        }
        System.out.printf("第三次排序:%s\n", Arrays.toString(arr));

    }
}
